package J3_28;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;

public class test {

    //给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。
    public int triangleNumber(int[] nums) {
        Arrays.sort(nums);
        int count = 0;
        for (int i = nums.length - 1; i >= 2; i--) {
            int num = nums[i];
            int l = 0, r = i - 1;
            while (l < r) {
                if (nums[l] + nums[r] > num) {
                    count += r - l;
                    r--;
                } else {
                    l++;
                }
            }
        }
        return count;
    }

    //给定一个含有 n 个正整数的数组和一个正整数 target 。
    //
    //找出该数组中满足其总和大于等于 target 的长度最小的 连续
    //子数组
    // [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
    //
    //
    public int minSubArrayLen(int target, int[] nums) {
        int l = 0;
        int r = 0;
        int sum = 0;
        int min = Integer.MAX_VALUE;
        while (r < nums.length) {
            sum += nums[r++];
            while (sum >= target) {
                min = Math.min(min, r - l);
                sum -= nums[l++];
            }
        }
        return min == Integer.MAX_VALUE ? 0 : min;
    }


    //给定一个字符串 s ，请你找出其中不含有重复字符的 最长
    //子串
    // 的长度
    public int lengthOfLongestSubstring(String s) {
        if (s.length() == 0) {
            return 0;
        }
        char[] ch = s.toCharArray();
        int max = 1;
        Queue<Character> queue = new ArrayDeque<>();
        for (char c : ch) {
            if (queue.contains(c)) {
                while (c != queue.poll()) ;
                queue.offer(c);
            } else {
                queue.offer(c);
                max = Math.max(max, queue.size());
            }
        }
        return max;
    }
}
